#include "Quicksort.h"

void swap(int* a_i, int* a_j)
{
	int temp = *a_i;
	*a_i = *a_j;
	*a_j = temp;
}

void quickSort(int* a, int* c, int dim)
{
	quickSortR(a, c, 0, dim - 1);
}

void quickSortR(int* a, int* c, int iniz, int fine)
{
	int i, j, iPivot, pivot;
	if (iniz < fine)
	{
		i = iniz;
		j = fine;
		iPivot = fine;
		pivot = a[iPivot];
		do /* find pivot position */
		{
			while (i < j && a[i] <= pivot) i++;
			while (j > i && a[j] >= pivot) j--;
			if (i < j)	//swap in both arrays
			{
				swap(&a[i], &a[j]);
				swap(&c[i], &c[j]);
			}
		}
		while (i < j);
		/* determination of sub-arrays */
		/* pivot positioning */
		if (i != iPivot && a[i] != a[iPivot])	//swap in both arrays
		{
			swap(&a[i], &a[iPivot]);
			swap(&c[i], &c[iPivot]);
			iPivot = i;
		}
		/* recursion on sub-arrays if is necessary */
		if (iniz < iPivot - 1)
			quickSortR(a, c, iniz, iPivot - 1);
		if (iPivot + 1 < fine)
			quickSortR(a, c, iPivot + 1, fine);
	} /* (iniz < fine) */
} /* quickSortR */